#include <iostream>
#include <vector>
#include <queue>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    TreeNode* building(vector<int>& preorder, vector<int>& inorder, int p1, int p2, int p3, int p4)
    {
        if (p3 <= 0 || p4 <= 0)
        {
            return nullptr;
        }
        int i = 0;
        for (; i < size(inorder) - p2; i++)
        {
            if (inorder[i + p2] == preorder[p1])
            {
                break;
            }
        }
        TreeNode* root = new TreeNode(preorder[p1]);
        root->left = building(preorder, inorder, p1 + 1, p2, i, i);
        root->right = building(preorder, inorder, p1 + i + 1, p2 + i + 1, p3 - i - 1, p4 - i - 1);
        return root;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int p3 = size(preorder);
        int p4 = size(inorder);
        TreeNode* root = building(preorder, inorder, 0, 0, p3, p4);
        return root;
    }
};

class Solution {
public:
    TreeNode* building(vector<int>& inorder, vector<int>& postorder, int p1, int p2, int p3, int p4)
    {
        if (p3 <= 0 || p4 <= 0)
        {
            return nullptr;
        }
        TreeNode* root = new TreeNode(postorder[p4 - 1]);
        int i = 0;
        for (i; i < size(inorder) - p1; i++)
        {
            if (inorder[i + p1] == postorder[p4 - 1])
            {
                break;
            }
        }
        root->left = building(inorder, postorder, p1, p2 + 1, i, i);
        root->right = building(inorder, postorder, p1 + i + 1, p2 + 1 + i, p3 - i - 1, p4 - 1);
        return root;
    }
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        int p3 = size(inorder);
        int p4 = size(postorder);
        return building(inorder, postorder, 0, 0, p3, p4);;
    }
};


class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;
    Node() : val(0), left(NULL), right(NULL), next(NULL) {}
    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}
    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};

class Solution {
public:
    Node* connect(Node* root) {
        if (root == nullptr)
        {
            return nullptr;
        }
        queue<Node*> q;
        root->next = nullptr;
        q.push(root->left);
        q.push(root->right);
        while (!q.empty())
        {
            Node* prev = nullptr;
            int num = q.size();
            while (num > 0)
            {
                Node* left = q.front();
                q.pop();
                Node* right = q.front();
                q.pop();
                if (left)
                {
                    if (prev)
                    {
                        prev->next = left;
                    }
                    prev = left;
                    prev->next = nullptr;
                    q.push(left->left);
                    q.push(left->right);
                }
                if (right)
                {
                    if (prev)
                    {
                        prev->next = right;
                    }
                    prev = right;
                    prev->next = nullptr;
                    q.push(right->left);
                    q.push(right->right);
                }
                num -= 2;
            }
        }
        return root;
    }
};

class Solution {
public:
    void flatten(TreeNode* root) {
        if (root == nullptr)
        {
            return;
        }
        flatten(root->left);
        flatten(root->right);
        if (root->left != nullptr)
        {
            auto prev = root->left;
            while (prev->right)
            {
                prev = prev->right;
            }
            prev->right = root->right;
            root->right = root->left;
            root->left = nullptr;
        }
    }
};

class Solution {
public:
    void SumTree(TreeNode* root)
    {
        if (root == nullptr)
        {
            return;
        }
        this->num = this->num * 10 + root->val;
        if (root->left == nullptr && root->right == nullptr)
        {
            vet.push_back(num);
            this->num /= 10;
            return;
        }
        SumTree(root->left);
        SumTree(root->right);
        this->num /= 10;
    }
    int sumNumbers(TreeNode* root) {
        SumTree(root);
        int n = vet.size();
        int ret = 0;
        for (int i = 0; i < n; i++)
        {
            ret += vet[i];
        }
        return ret;
    }
    vector<int> vet;
    int num = 0;
};

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> ret;
        if (root == nullptr)
        {
            return ret;
        }
        ret.push_back(root->val);
        queue<TreeNode*> q;
        q.push(root->left);
        q.push(root->right);
        while (!q.empty())
        {
            TreeNode* prev = nullptr;
            int n = q.size();
            while (n > 0)
            {
                TreeNode* left = q.front();
                q.pop();
                TreeNode* right = q.front();
                q.pop();
                if (left)
                {
                    prev = left;
                    q.push(left->left);
                    q.push(left->right);
                }
                if (right)
                {
                    prev = right;
                    q.push(right->left);
                    q.push(right->right);
                }
                n -= 2;
            }
            if (prev)
            {
                ret.push_back(prev->val);
            }
        }
        return ret;
    }
};